package JavaStructure.LinkedList;
import java.util.Scanner;


public class Practice {
    //Leecode.21. 合并两个有序链表
    public MyLinkedList.ListNode mergeTwoLists(MyLinkedList.ListNode list1, MyLinkedList.ListNode list2) {
        MyLinkedList.ListNode headJ = new MyLinkedList.ListNode(0);
        MyLinkedList.ListNode MoveHead = headJ;

        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                MoveHead.next = list1;
                list1 = list1.next;
            } else {
                MoveHead.next = list2;
                list2 = list2.next;
            }
            MoveHead = MoveHead.next;
        }

        if (list1 != null) {
            MoveHead.next = list1;
        }

        if (list2 != null) {
            MoveHead.next = list2;
        }

        return headJ.next;
    }


    //链表的回文结构
    public int PalindromeStructure(MyLinkedList.ListNode head) {
        //找到中间节点
        MyLinkedList.ListNode slow = head;
        MyLinkedList.ListNode fast = head;

        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        //将后半部分的节点逆转过来
        MyLinkedList.ListNode temp = slow.next;
        MyLinkedList.ListNode tempN = temp.next;
        while (tempN != null) {
            tempN = tempN.next;
            slow.next = temp;
            slow = slow.next;
            temp = tempN;
        }

        //判断回文
        while (slow != head) {
            slow = slow.next;
            head = head.next;
            if (slow.val == head.val) {
                return -1;
            }
        }
        return 1;
    }
}
